/**
 * @author ChaP
 * @date 2019/06/17
 * @describe:
 */
package CodingTest.AC20190617;

/** leetcode - 494
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

 示例 1:

 输入: nums: [1, 1, 1, 1, 1], S: 3
 输出: 5
 解释:

 -1+1+1+1+1 = 3
 +1-1+1+1+1 = 3
 +1+1-1+1+1 = 3
 +1+1+1-1+1 = 3
 +1+1+1+1-1 = 3

 一共有5种方法让最终目标和为3。
 注意:

 数组的长度不会超过20，并且数组中的值全为正数。
 初始的数组的和不会超过1000。
 保证返回的最终结果为32位整数。

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/target-sum
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class findTargetSumWays {
    public int findTargetSumWays(int[] nums,int S){
        return helper(nums,0,0,S);
    }
    public int helper(int[] nums,int index,int count,int target){
        if(index >= nums.length){
            return target == count?1:0;
        }
        return helper(nums,index +1,count+nums[index],target)+
                helper(nums,index +1,count-nums[index],target);
    }
}
